/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int averageOfSubtree(TreeNode* root) {
        int ans = 0;
        // if(root != nullptr)
            dfs(root, ans);
        return ans;
    }

    void dfs(TreeNode* cur, int& ans){
        if(cur == nullptr) return ;
        // 叶子节点的情况一定得 ans++ 的哦
        // if(cur->left == nullptr && cur->right == nullptr){
        //     ans++;
        //     return;
        // }

        // 基本的方式：前序遍历从上往下遍历每一个节点作为root，的前提下再前序遍历去求当前root树的节点的总和和节点数量的总和
        // 所以时间复杂度是: O(n^2)

        // 递归左右子树计算左右子树的节点的和sum，判断root->val是否等于sum
        // 是向下取整的哦，注意平均值哦
        // 是不用碰到叶子的情况的哦，因为下面的 nodesum = 1, 以及 sum 最开始就加上了一个 cur->val。
        // 都是把以当前节点为一颗树，cur 节点作为 root 节点去处理的。(不然还得处理下面的 sum / nodesum 有除零的异常去处理的哦)
        int nodesum = 1;
        int sum = cur->val + sumdfs(cur->left, nodesum) + sumdfs(cur->right, nodesum);
        
        // 用下面的方法还是更好理解的哦：通过前序遍历的方式依次遍历整棵树的过程中，去处理 自己想要处理的任务。
        // sum 和 nodesum 就相当于是搭上了一个顺风车
        // int sum = 0, nodesum = 0;
        // sumdfs(cur, sum, nodesum);
        if(cur->val == (sum / nodesum)) ans++;   
        dfs(cur->left, ans);
        dfs(cur->right, ans);
    }

    int sumdfs(TreeNode* cur, int& nodesum){
        if(cur == nullptr) return 0;
        nodesum++;
        return cur->val + sumdfs(cur->left, nodesum) + sumdfs(cur->right, nodesum);
    }
    // void sumdfs(TreeNode* cur, int &sum, int &nodesum){
    //     if(cur == nullptr) return;
    //     sum = sum + cur->val;
    //     nodesum++;
    //     sumdfs(cur->left, sum, nodesum);
    //     // sumdfs(cur->left, sum, nodesum);
    //     sumdfs(cur->right, sum, nodesum);
    // }
};

